package vip.zhenzicheng.algorithm.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/3sum/">三数之和 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-16 10:42
 */
public class ThreeSum_15 {

  /*双指针+双循环*/
  public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums.length < 3) { // 三数之和所以必须有三个数
      return result;
    }
    Arrays.sort(nums); // 升序排序


    int head, tail; // 头尾双指针
    for (int i = 0, temp; i < nums.length - 2; i++) { // 空出双指针
      if (nums[i] > 0) {
        return result; // a + b + c > 0;在升序数组中a>0则一定不成立
      }
      head = i + 1;
      tail = nums.length - 1;

      while (head < tail) {
        temp = nums[i] + nums[head] + nums[tail]; // 计算当前合
        if (temp < 0) {
          head++;
        } else if (temp > 0) {
          tail--;
        } else {
          List<Integer> l = new ArrayList<>(3);
          l.add(nums[i]);
          l.add(nums[head]);
          l.add(nums[tail]);
          result.add(l);

          // 去重head
          while (head < tail && nums[head] == nums[head + 1]) {
            head++;
          }
          head++;
          // 去重tail
          while (head < tail && nums[tail] == nums[tail - 1]) {
            tail--;
          }
          tail--;
        }
      }
      // 对i去重
      while (i + 1 < nums.length && nums[i] == nums[i + 1]) {
        i++;
      }
    }

    return result;
  }
}
